package com.atguigu.sort;

import java.util.Arrays;

/**
 * 希尔排序
 * 仅示范移动法即可
 *
 * 耗时:
 * work: 1.2s
 */
public class ShellSort {
    public static void main(String[] args) {
//        int[] arr={8,9,1,7,2,3,5,4,6,0};
        int[] arr=ArrCreator.createRandArr(ArrCreator.testVelocitySize);
//        System.out.println(Arrays.toString(arr));
        ArrCreator.beforeSort();
        sort(arr);
        ArrCreator.afterSort();
//        System.out.println(Arrays.toString(arr));
    }

    /**
     * 希尔算法
     *
     * 可行性无须讨论, 因为有最后一轮实际上的插入排序保底
     *
     * 实测耗时并不比插入排序高, 推测可能与计算机的某些计算结构有关系
     *
     * 尽管理论上感觉, 这种算法比原始插入排序, 所需的插入频率更低
     *
     *
     *
     * @param arr
     */
    public static void sort(int[] arr){
//        int temp;
//        int groupCount;
        int count=0;
        int insertVal;
        int insertIndex;
        // gap: 5, 2, 1
        for(int gap=arr.length/2;gap>0;gap/=2){
            // groupCount: 2, 5, 10
//            groupCount=(arr.length-1)/gap+1;
            // 每轮新gap, 对每组数据进行插入排序
            for(int i=gap;i<arr.length;i+=gap){
                insertVal=arr[i];
                insertIndex=i-gap;
                while(insertIndex>=0&&insertVal<arr[insertIndex]){
                    arr[insertIndex+gap]=arr[insertIndex];
                    insertIndex-=gap;
                }
                arr[insertIndex+gap]=insertVal;
//                for(int j=i+gap;j>=gap;j-=gap){
//                    if (arr[j]<arr[j-gap]) {
//                        temp=arr[j];
//                        arr[j]=arr[j-gap];
//                        arr[j-gap]=temp;
//                        break;
//                    }
//                }
            }
//            System.out.println("第"+(++count)+"轮:"+Arrays.toString(arr));
        }
    }
}
